6、贪心 &区间问题

AcWing 905. 区间选点

AcWing 908. 最大不相交区间数量

AcWing 906. 区间分组

AcWing 907. 区间覆盖

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();

    }
    class Range implements Comparable {
        int l,r;

        public Range(int l,int r){
            this.l=l;
            this.r=r;
        }
        @Override
        public int compareTo(Object o) {
            Range range= (Range) o;
            return r-range.r;
        }
    }
    ArrayList<Range> queue=new ArrayList();
    void init(){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for (int i = 0; i < n; i++) {
            int l=sc.nextInt();
            int r=sc.nextInt();
            queue.add(new Range(l,r));
        }
        Collections.sort(queue);
        int now_roit= (int) -0x3f3f3f3f;
        int res=0;
        for (Range range : queue) {
            if(!(now_roit>=range.l&&now_roit<=range.r)){
                now_roit=range.r;
                res++;
            }
        }
        System.out.println(res);
    }

}

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();

    }
    class Range implements Comparable {
        int l,r;

        public Range(int l,int r){
            this.l=l;
            this.r=r;
        }
        @Override
        public int compareTo(Object o) {
            Range range= (Range) o;
            return r-range.r;
        }
    }
    ArrayList<Range> queue=new ArrayList();
    void init(){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for (int i = 0; i < n; i++) {
            int l=sc.nextInt();
            int r=sc.nextInt();
            queue.add(new Range(l,r));
        }
        Collections.sort(queue);
        int now_roit= (int) -0x3f3f3f3f;
        int res=0;
        for (Range range : queue) {
            if(!(now_roit>=range.l&&now_roit<=range.r)){
                now_roit=range.r;
                res++;
            }
        }
        System.out.println(res);
    }

}

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();

    }

    class Range implements Comparable {
        int l, r;

        public Range(int l, int r) {
            this.l = l;
            this.r = r;
        }

        @Override
        public int compareTo(Object o) {
            Range range = (Range) o;
            return l - range.l;
        }
    }

    ArrayList<Range> queue = new ArrayList();
    //    构造大顶堆：
    PriorityQueue<Integer> small_heap
            = new PriorityQueue<>();

    void init() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            queue.add(new Range(l, r));
        }
        Collections.sort(queue);
        for (int i = 0; i < queue.size(); i++) {
            if (small_heap.isEmpty()) small_heap.offer(queue.get(i).r);
            else {
                //没有交集，加在一起
                if (small_heap.peek() < queue.get(i).l) {
                    small_heap.poll();
                    small_heap.offer(queue.get(i).r);
                } else {
                    //有交集，直接新开
                    small_heap.offer(queue.get(i).r);
                }
            }
        }
        System.out.println(small_heap.size());
    }
}

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();

    }

    class Range implements Comparable {
        int l, r;

        public Range(int l, int r) {
            this.l = l;
            this.r = r;
        }

        @Override
        public int compareTo(Object o) {
            Range range = (Range) o;
            return l - range.l;
        }
    }

    ArrayList<Range> arrayList = new ArrayList();
    //    构造大顶堆：
    PriorityQueue<Integer> small_heap
            = new PriorityQueue<>();

    void init() {
        Scanner sc = new Scanner(System.in);
        int startstart = sc.nextInt();
        int endend = sc.nextInt();
        int N= sc.nextInt();
        for (int i = 0; i < N; i++) {
            arrayList.add(new Range(sc.nextInt(),sc.nextInt()));
        }
        Collections.sort(arrayList);
        int start=startstart,end=endend;
        int res=0;
        boolean no=true;
        while(true){
            int max= (int) -1e9;
            Range range_max=null;
            int max_i=0;
            for (int i = 0; i < arrayList.size(); i++) {
                if(arrayList.get(i).l<=start&&arrayList.get(i).r>=start){
                    if(arrayList.get(i).r>max){
                        max= arrayList.get(i).r;
                        range_max=arrayList.get(i);
                        max_i=i;
                    }
                }
            }
            if(range_max==null){
                no=false;
                break;
            }
            arrayList.remove(max_i);
            start=range_max.r;
            if(range_max.r<end){
                res++;
            }else break;
        }
        if(no==false) System.out.println(-1);
        else System.out.println(++res);
    }
}